package problems;

import java.util.ArrayList;
import java.util.List;

import lib.MathLib;

public class Euler092 extends AbstractEuler {

	@Override
	public Number calculate() {

		//none of the numbers in the range 1..9999999 has a sum of squares greater than 9999999,
		//so determining the end result of all chains starting at 1..623 (7 * 9^2) will be enough

		Boolean[] leadsTo89 = new Boolean[7 * 9 * 9 + 1];

		leadsTo89[1] = Boolean.FALSE;
		leadsTo89[89] = Boolean.TRUE;
		
		for (int i = 1; i <= 7 * 9 * 9; i++) { 
			List<Integer> chain = new ArrayList<Integer>();
			chain.add(i);
			int squareOfDigits = i;
			Boolean chainLeadsTo89 = leadsTo89[squareOfDigits];
			
			while (chainLeadsTo89 == null) {
				squareOfDigits = MathLib.sumOfDigitsRaisedToPower(squareOfDigits, 2);
				chainLeadsTo89 = leadsTo89[squareOfDigits];
				chain.add(squareOfDigits);
			}

			for (int value : chain) {
				leadsTo89[value] = chainLeadsTo89;
			}
		}
		
		
		int sadNumbers = 0;
		

		//TODO: optimize; 123 has the same sum of squares as 321, etc. for all 6 permutations.
		//there are 10 ways to add one digit to 123, 
		//Let the number of ways of writing n as the sum of k squares be f(n,k). Then f can be computed by the recurrence relation:
		//f(n,k) = f(n-0^2,k-1) + f(n-1^2,k-1) + f(n-2^2,k-1) + .... + f(n-9^2,k-1)

		
		//now count the number of values whose square of digits leads to 89, eventually.
		for (int i = 1; i < Math.pow(10, 7); i++) {
			if (leadsTo89[MathLib.sumOfDigitsRaisedToPower(i,2)]) sadNumbers++;
		}
		
		return sadNumbers;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 8581146;
	}

}
